class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: list) -> list:
        # 要先排除不在的情况
        if endWord not in wordList:
            return []
        self.flag = True
        # 下面这个字典键保存当前次所有的可能情况,后面的列表保存所有路径
        res_dic_start, res_dic_end = {beginWord: [[beginWord]]}, {endWord: [[endWord]]}
        set_through_start, set_through_end = set(), set()
        self.word_len, self.word_set = len(beginWord), set(wordList)  # 变成集合在查找的时候省时间
        # 从开头开始查找和从结尾开始查找是等价的,所以哪个短从那个开始查找
        while self.flag:
            if len(res_dic_start) <= len(res_dic_end):
                res_dic_start = self.find_next(res_dic_start, res_dic_end, set_through_start)
            else:
                res_dic_end = self.find_next(res_dic_end, res_dic_start, set_through_end)
        # 字典在遍历的时候不能删除,因此需要弄一个新字典保存结果
        res = []
        for word in res_dic_start:
            if word in res_dic_end:
                for lists1 in res_dic_start[word]:
                    for lists2 in res_dic_end[word]:
                        res.append(lists1 + lists2[-2::-1])
        return res

    def find_next(self, dic_in, dic_tar, set_in):
        """对进来的第一个字典执行一次查找操作,并判断结果在不在第二个字典里,如果在就是找到了
        找完之后,将中间字典返回回去,再由调用函数赋值给第一个字典,完成一次迭代
        外面传的时候互换两个字典的位置,就可以用一个函数完成从前从后查找的功能
        """
        # TODO: 加两个集合,存储之前已经到达的字符,可以减少检索次数
        mid_res, mid_set = {}, set()
        for word in dic_in:
            # 这里查找字符没有找到比较好的方法,只能写两个循环穷举
            for i in range(self.word_len):
                for alpha in "abcdefghijklmnopqrstuvwxyz":
                    mid_word = word[:i] + alpha + word[i + 1:]
                    if mid_word not in set_in and mid_word not in dic_in[word][0]:
                        # 如果变的字符在第二个字典里面,就是找到了;因为要找所有,所以这轮查找要做完
                        if mid_word in dic_tar:
                            self.flag = False
                        if mid_word in self.word_set:
                            mid_set.add(mid_word)
                            if mid_word not in mid_res:
                                mid_res[mid_word] = []
                            for lists in dic_in[word]:
                                mid_res[mid_word].append(lists + [mid_word])
        set_in.update(mid_set)
        if len(mid_res) == 0:
            self.flag = False
        return mid_res


a = Solution()
print(a.findLadders(beginWord="hit", endWord="cog", wordList=["hot", "dot", "dog", "lot", "log", "cog"]))
print(a.findLadders(beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]))
print(a.findLadders(beginWord = "talk", endWord = "tail", wordList = ["talk","tons","fall","tail","gale","hall","negs"]))
print(a.findLadders(beginWord = "cet", endWord = "ism", wordList=["kid","tag","pup","ail","tun","woo","erg","luz",
"brr","gay","sip","kay","per","val","mes","ohs","now","boa","cet","pal","bar","die","war","hay","eco","pub","lob",
"rue","fry","lit","rex","jan","cot","bid","ali","pay","col","gum","ger","row","won","dan","rum","fad","tut","sag",
"yip","sui","ark","has","zip","fez","own","ump","dis","ads","max","jaw","out","btu","ana","gap","cry","led","abe",
"box","ore","pig","fie","toy","fat","cal","lie","noh","sew","ono","tam","flu","mgm","ply","awe","pry","tit","tie",
"yet","too","tax","jim","san","pan","map","ski","ova","wed","non","wac","nut","why","bye","lye","oct","old","fin",
"feb","chi","sap","owl","log","tod","dot","bow","fob","for","joe","ivy","fan","age","fax","hip","jib","mel","hus",
"sob","ifs","tab","ara","dab","jag","jar","arm","lot","tom","sax","tex","yum","pei","wen","wry","ire","irk","far",
"mew","wit","doe","gas","rte","ian","pot","ask","wag","hag","amy","nag","ron","soy","gin","don","tug","fay","vic",
"boo","nam","ave","buy","sop","but","orb","fen","paw","his","sub","bob","yea","oft","inn","rod","yam","pew","web",
"hod","hun","gyp","wei","wis","rob","gad","pie","mon","dog","bib","rub","ere","dig","era","cat","fox","bee","mod",
"day","apr","vie","nev","jam","pam","new","aye","ani","and","ibm","yap","can","pyx","tar","kin","fog","hum","pip",
"cup","dye","lyx","jog","nun","par","wan","fey","bus","oak","bad","ats","set","qom","vat","eat","pus","rev","axe",
"ion","six","ila","lao","mom","mas","pro","few","opt","poe","art","ash","oar","cap","lop","may","shy","rid","bat",
"sum","rim","fee","bmw","sky","maj","hue","thy","ava","rap","den","fla","auk","cox","ibo","hey","saw","vim","sec",
"ltd","you","its","tat","dew","eva","tog","ram","let","see","zit","maw","nix","ate","gig","rep","owe","ind","hog",
"eve","sam","zoo","any","dow","cod","bed","vet","ham","sis","hex","via","fir","nod","mao","aug","mum","hoe","bah",
"hal","keg","hew","zed","tow","gog","ass","dem","who","bet","gos","son","ear","spy","kit","boy","due","sen","oaf",
"mix","hep","fur","ada","bin","nil","mia","ewe","hit","fix","sad","rib","eye","hop","haw","wax","mid","tad","ken",
"wad","rye","pap","bog","gut","ito","woe","our","ado","sin","mad","ray","hon","roy","dip","hen","iva","lug","asp",
"hui","yak","bay","poi","yep","bun","try","lad","elm","nat","wyo","gym","dug","toe","dee","wig","sly","rip","geo",
"cog","pas","zen","odd","nan","lay","pod","fit","hem","joy","bum","rio","yon","dec","leg","put","sue","dim","pet",
"yaw","nub","bit","bur","sid","sun","oil","red","doc","moe","caw","eel","dix","cub","end","gem","off","yew","hug",
"pop","tub","sgt","lid","pun","ton","sol","din","yup","jab","pea","bug","gag","mil","jig","hub","low","did","tin",
"get","gte","sox","lei","mig","fig","lon","use","ban","flo","nov","jut","bag","mir","sty","lap","two","ins","con",
"ant","net","tux","ode","stu","mug","cad","nap","gun","fop","tot","sow","sal","sic","ted","wot","del","imp","cob",
"way","ann","tan","mci","job","wet","ism","err","him","all","pad","hah","hie","aim","ike","jed","ego","mac","baa",
"min","com","ill","was","cab","ago","ina","big","ilk","gal","tap","duh","ola","ran","lab","top","gob","hot","ora",
"tia","kip","han","met","hut","she","sac","fed","goo","tee","ell","not","act","gil","rut","ala","ape","rig","cid",
"god","duo","lin","aid","gel","awl","lag","elf","liz","ref","aha","fib","oho","tho","her","nor","ace","adz","fun",
"ned","coo","win","tao","coy","van","man","pit","guy","foe","hid","mai","sup","jay","hob","mow","jot","are","pol",
"arc","lax","aft","alb","len","air","pug","pox","vow","got","meg","zoe","amp","ale","bud","gee","pin","dun","pat",
"ten","mob"]))
